package com.yaoli.base;

/**
 * Created by YaoLi on 2017/8/16.
 *
 */
public class FastPaiXu {
    public static void main(String[] args) {
        char [] a = String.valueOf("0123").toCharArray();
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i] - 48);
        }

        System.out.println((int)Math.pow(10,2));

//        int [] suiji = new int[1000000];
        int [] suiji = {12,10,12,1,12,11,12,10,12,1,12,11};

//        for (int i = 0; i < suiji.length; i++) {
//            suiji[i] = (new Random()).nextInt(1000000);
//            //System.out.print(suiji[i]+"\t");
//        }

        int temp [] = suiji.clone();

        FastPaiXu fastPaiXu = new FastPaiXu();

        long begin = System.currentTimeMillis();
        fastPaiXu.sort(suiji,0,suiji.length - 1);
        long end = System.currentTimeMillis();
        System.out.println("");
        System.out.println(end - begin);

//        begin = System.currentTimeMillis();
//        Arrays.sort(temp);
//        end = System.currentTimeMillis();
//        System.out.println(end - begin);

        for (int i = 0; i < suiji.length; i++) {
            System.out.print(suiji[i]+"\t");
        }

    }

    /**
     * 基本排序
     */
    public void sort(int [] array,int begin ,int end){
        if(begin >= end){
            return;
        }
        int tb = begin;
        int te = end;

        int pivot = begin;//这里只记住了指针的位置，而并没有记住值

        while(begin < end){

            //切记一定要从后面开始
            while(begin < end && array[pivot] <= array[end]){
                end--;
            }
            //交换指针所在的值
            swap(array,end,pivot);

            //将最后一个赋值给轴
            pivot = end;

            //从头开始比较
            while(begin < end && array[begin] <= array[pivot]){
                begin++;
            }

            swap(array,begin,pivot);
            //将最后一个富于轴
            pivot = begin;

        }

        sort(array,tb,pivot - 1);
        sort(array,pivot + 1,te);

    }

    public void swap(int [] array , int i , int j){
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

}
